package medium;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2022/3/27 14:07
 */
public class No78_子集 {
    public static void main(String[] args) {
        Solution78 solution78 = new Solution78();
        int[] nums = new int[]{1, 2, 3};
        List<List<Integer>> subsets = solution78.subsets(nums);
        System.out.println(subsets);
    }   
}

class Solution78 {
    public List<List<Integer>> subsets(int[] nums) {
        //获取形如0000-1111这样的东西
        int allCheck = 1 << nums.length;
        List<List<Integer>> res = new ArrayList<>();
        //遍历
        for (int check = 0; check < allCheck; check++) {
            // check: 1010 
            //右移的个数用来找索引
            List<Integer> data =  new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                int lastNumber = check >> i;
                //判断最后一个是不是1,如果是1,则加入,由于镜像,因此结果无影响
                if ((lastNumber & 1) == 1) {
                    //则加入,镜像索引
                    data.add(nums[i]);
                }
            }
            res.add(data);
        }
        return res;
    }
}



    //public List<List<Integer>> subsets(int[] nums) {
    //    //No46.全排列 动态规划
    //    //定义dp数组
    //    List<List<Integer>>[] dp = new ArrayList[nums.length + 1];
    //    //定义res,存放所有子集
    //    List<List<Integer>> res = new ArrayList<>();
    //    //初始化dp数组
    //    for (int i = 0; i < dp.length; i++) {
    //        dp[i] = new ArrayList<>();
    //    }
    //    
    //    //空集加入
    //    dp[0].add(new ArrayList<>());
    //    res.addAll(dp[0]);
    //    
    //    //开始处理dp
    //    for (int index = 1; index < dp.length; index++) {
    //        //这部分是处理每一个dp元素
    //        //假定这时候index = 3,即要计算 [123][124][234]
    //        //获取dp[index-1] 的所有元素 [12] [23] [13]
    //        List<List<Integer>> preList = dp[index - 1];
    //        //对每个元素都遍历nums数据
    //        for (List<Integer> preData : preList) {
    //            //preData: [23]
    //            for (int num : nums) {
    //                // 1234
    //                //升序去重
    //                if (preData.size() == 0 || preData.get(preData.size() - 1) < num) {
    //                    //值传递问题
    //                    List<Integer> dataCopy = new ArrayList<>(preData);
    //                    // dataCopy:[234]
    //                    dataCopy.add(num);
    //                    dp[index].add(dataCopy);
    //                    res.add(dataCopy);
    //                }
    //            }
    //        }
    //        
    //    }
    //    return res;
    //}



    //public List<List<Integer>> subsets(int[] nums) {
    //    //No77 [1,2,3,4,5,6,7,8] k=4 
    //    //No77 [1,2,3,4,5,6,7,8] k=0,1,2,3,4,5,6,7,8
    //    Map<Integer, String> checkMap = new HashMap<>();
    //    //遍历数组,初始化元素为未使用状态
    //    for (int i = 0; i < nums.length; i++) {
    //        checkMap.put(nums[i], "未使用");
    //    }
    //
    //    List<Integer> sortData = new ArrayList<>();
    //    List<List<Integer>> 临时结果 = new ArrayList<>();
    //    
    //    //如何获取全集
    //    List<List<Integer>> 最终结果 = new ArrayList<>();
    //    for (int k = 1; k <= nums.length; k++) {
    //        subsets(nums, k, checkMap, sortData, 临时结果);
    //        最终结果.addAll(临时结果);
    //        临时结果.clear();
    //    }
    //
    //    最终结果.add(new ArrayList<>());
    //    return 最终结果;
    //}
    //
    //
    ////获取k个元素组成的子集
    //public void subsets(int[] nums, int k, Map<Integer, String> checkMap,
    //                    List<Integer> sortData,
    //                    List<List<Integer>> 临时结果) {
    //
    //
    //    if (k == 0) {
    //        //这时候扔
    //        //注意值传递:
    //        List<Integer> sortDataCopy = new ArrayList<>(sortData);
    //        临时结果.add(sortDataCopy);
    //        return;
    //    }
    //    
    //    //遍历map
    //    for (Map.Entry<Integer, String> mapData : checkMap.entrySet()) {
    //        //当前元素
    //        Integer currentKey = mapData.getKey();
    //        if (!checkMap.get(currentKey).equals("阿迪开发的")) {
    //            if (sortData.size() == 0 || sortData.get(sortData.size() - 1) < currentKey) {
    //                //已使用
    //                checkMap.put(currentKey, "阿迪开发的");
    //                //sortData.add(currentKey)的前提
    //                //sortData:7,10,11 13
    //                sortData.add(currentKey);
    //                //下一波
    //                subsets(nums, k - 1, checkMap, sortData,临时结果);
    //                //回溯
    //                checkMap.put(currentKey, "未使用");
    //                sortData.remove(sortData.size() - 1);
    //            }
    //        }
    //
    //    }
    //}





